package HashTable;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _554_BrickWall {
    public int leastBricks_o(List<List<Integer>> wall) {
        Map<Integer, Integer> bricks = new HashMap<>();
        Map<Integer, Integer> bpos = new HashMap<>();
        int totalWidth = 0;
        int totalLength = wall.size();
        int min = totalLength;
        for (int width : wall.get(0)) {
            totalWidth += width;
        }
        //initial bricks
        for (int i = 0; i < totalLength; i++) {
            bricks.put(i, wall.get(i).get(0));
            bpos.put(i, 0);
        }
        //over time limited
        for (int i = 1; i < totalWidth; i++) {
            int count = totalLength;
            for (int j = 0; j < totalLength; j++) {
                if (bricks.get(j) == i) {
                    count--;
                    int newPos = bpos.get(j) + 1;
                    int newVal = bricks.get(j) + wall.get(j).get(newPos);
                    bricks.put(j,newVal);
                    bpos.put(j, newPos);
                } else if (bricks.get(j) < i) {
                    int newPos = bpos.get(j) + 1;
                    int newVal = bricks.get(j) + wall.get(j).get(newPos);
                    bricks.put(j,newVal);
                    bpos.put(j, newPos);
                }
            }
            //update min
            if (count < min) {
                min = count;
            }
        }
        return min;
    }

    //loop per length
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> ends = new HashMap<>();
        int max = 0;
        int length = wall.size();
        for (int i = 0; i < length; i++) {
            int sum = 0;
            for (int j = 0; j + 1 < wall.get(i).size(); j++) {
                sum += wall.get(i).get(j);
                ends.put(sum, ends.getOrDefault(sum, 0) + 1);
                max = Math.max(max, ends.get(sum));
            }
        }
        return wall.size() - max;
    }
}
